package com.example.demo.arithmetic.algorithm.dynamic_programing;

/**
 * leetcode96
 * 卡特兰数
 * 给定一个整数n 求由n个节点从1到n互不相同的二叉搜索树有多少种？
 * 二茬搜索树：每一个节点，坐标的节点总是小于该节点，右边的节点总是大于该节点
 */
public class Catalan {
    /**
     * 递归慢的很
     *
     * @param n
     * @return
     */
    public int catalan1(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            //            System.out.print(i-1+" ");
            //            System.out.print(5-i);
            //            System.out.println();
            sum += catalan(i - 1) * catalan(n - i);
        }
        return sum;
    }

    public int catalan(int n) {
//        if (n == 0 || n == 1) {
//            return 1;
//        }
//        int sum = 0;
//        for (int i = 1; i <= n; i++) {
//            //            System.out.print(i-1+" ");
//            //            System.out.print(5-i);
//            //            System.out.println();
//            sum += catalan(i - 1) * catalan(n - i);
//        }
//        return sum;
        int sum = 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int j = 2; j < n + 1; j++) {
            for (int i = 0; i < j; i++) {
                dp[j] += dp[i] * dp[j - 1 - i];
            }
            System.out.println(dp[j]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(new Catalan().catalan(5));
    }
}
